public class Solution97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length()!=s1.length()+s2.length()){
            return false;
        }
        boolean[][] f=new boolean[s1.length()+1][s2.length()+1];
        for (int i=0;i<=s1.length();i++){
            for (int j=0;j<=s2.length();j++){
                f[i][j]=i>0&&f[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)
                        ||j>0&&f[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1);
                if (i==0 && j==0){
                    f[i][j]=true;
                }
            }
        }
        return f[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution97().isInterleave("aabcc","dbbca","aadbbcbcac"));
    }
}
